﻿package kizzo.datastruct 
{		
	
	public class BinaryTree 
	{
		private var root:BinaryTreeNode;
		
		public var length:uint;
		public var depth:uint;		
		
		public function BinaryTree() 
		{
			this.length = 0;
			this.depth = 0;
		}
		
		/*
		 * Adds a node to the tree. If the addition exceeds the maximum allowed difference for depths of leaf nodes
		 * an automatic rebalance will be executed. The node added should have a unique key.
		 * @see noBalanceAdd noBalanceAdd
		 */
		public function add(node:BinaryTreeNode):void
		{				
			if (this.root != null)
			{				
				var current_node:BinaryTreeNode = this.root;
				var new_depth:uint = 1;
				
				while(1)
				{
					new_depth ++;
					if (node.key > current_node.key)
					{					
						if (current_node.hasRight())
							current_node = current_node.getRight();
						else
						{
							current_node.setRight(node);
							node.setParent(current_node);
							break;
						}
					}
					else if (node.key < current_node.key)
					{					
						if (current_node.hasLeft())
							current_node = current_node.getLeft();
						else
						{						
							current_node.setLeft(node);
							node.setParent(current_node);
							break;
						}
					}
					else
					{						
						return;
					}
				}
				
				if (new_depth > this.depth)
					this.depth = new_depth;
				
				this.length ++;
				
				if ((this.length < Math.pow(2, this.depth-10)))
					this.balance();
			}
			else
			{
				this.root = node;
				this.length = 1;
				this.depth = 1;
			}			
		}		
		
		/*
		 * Finds and returns node with key: "key"
		 */
		public function find(key:uint):BinaryTreeNode
		{			
			if (this.root != null)
			{
				var current_node:BinaryTreeNode = this.root;
				
				while(1)
				{					
					if (key > current_node.key)
					{					
						if (current_node.hasRight())
							current_node = current_node.getRight();
						else						
							return null;						
					}
					else if (key < current_node.key)
					{					
						if (current_node.hasLeft())
							current_node = current_node.getLeft();
						else
							return null;
					}
					else
					{
						return current_node;
					}
				}
			}
			return null;
		}
		
		/*
		 * Adds a node without performing automatic balancing of the tree whenever the treshold 
		 * defined by the difference between the minimum and maximum depth of leaf node is exceeded.
		 * This method gives more flexibility to decide when you want balancing to be performed.
		 * The node added should have a unique key.
		 */
		public function noBalanceAdd(node:BinaryTreeNode):void
		{				
			if (this.root != null)
			{				
				var current_node:BinaryTreeNode = this.root;
				var new_depth:uint = 1;
				
				while(1)
				{
					new_depth ++;
					if (node.key > current_node.key)
					{					
						if (current_node.hasRight())
							current_node = current_node.getRight();
						else
						{
							current_node.setRight(node);
							node.setParent(current_node);
							break;
						}
					}
					else if (node.key < current_node.key)
					{					
						if (current_node.hasLeft())
							current_node = current_node.getLeft();
						else
						{						
							current_node.setLeft(node);
							node.setParent(current_node);
							break;
						}
					}
					else
					{
						return;
					}
				}
				
				if (new_depth > this.depth)
					this.depth = new_depth;
				
				this.length ++;				
			}
			else
			{
				this.root = node;
				this.length = 1;
				this.depth = 1;
			}			
		}
		
		/*
		 * Balances the binary tree. This function is slow and its best to call it once most of the elements 
		 * have been added and mostly searches will be made.
		 */
		public function balance():void		
		{					
			if (this.length < 3)
			{
				//return;
			}
			else
			{
				var sorted_list:Array = [];								
				this.traverseTree(sorted_list.push);				
				this.root = null;
				this.length = 0;
				this.depth = 0;				
				array_to_tree(sorted_list,0,sorted_list.length-1);
			}		
		}
		
		private function array_to_tree(array:Array, from:int, to:int):void
		{
			if ((to - from) == 0)
			{
				this.noBalanceAdd(new BinaryTreeNode(array[from].key));
			}
			else if ((to - from) > 0)
			{					
				var mid_point:uint = from + (to - from ) / 2;				
				this.noBalanceAdd(new BinaryTreeNode(array[mid_point].key));
				array_to_tree(array, from, mid_point - 1);
				array_to_tree(array, mid_point + 1, to);
			}
		}
		
		/*
		 * Traverses the tree and performs node_operation function on each of its nodes. The traversal is
		 * in left-operation-right format - meaning that nodes are visited in ascending order of their keys.
		 */
		public function traverseTree(node_operation:Function):void
		{
			visit_node(this.root, node_operation);
		}
		
		
		private function visit_node(node:BinaryTreeNode, node_operation:Function):void
		{
			if (node.hasLeft())
				visit_node(node.getLeft(), node_operation);	
				
			node_operation.apply(this, [node]);
			
			if (node.hasRight())
				visit_node(node.getRight(), node_operation);	
		}				
		
		/*
		 * Traces a tree node in text format.
		 */
		public  function traceNode(node:BinaryTreeNode):void
		{
			if (node != null)
			if (node == this.root)
				trace(node.key + " Root");			
			else
				trace(node.key + " parent: " + node.getParent().key);			
		}
		
	}
	
}